package com.zhaopin.tree;

/**
 * @author yin.peide
 * @date 2021-06-17 10:40
 *
 * 判断一颗二叉树是否为 搜索二叉树
 */
//主函数
public class SearchBinaryTree {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node4.setLeft(node2);
        node4.setRight(node6);
        node2.setLeft(node1);
        node2.setRight(node3);
        node6.setLeft(node5);
        node6.setRight(node7);
        new SearchBinaryTree().checkIsSearch(node4);
    }

    //辅助变量：成员变量，所有递归栈共享
    int temp;
    boolean flag = true;

    //判断是否是搜索二叉树，中序遍历
    public void checkIsSearch(TreeNode treeNode) {
        temp = Integer.MIN_VALUE;
        this.inOrderRecru(treeNode);
        if (flag) {
            System.out.println("是搜索二叉树");
        } else {
            System.out.println("不是搜索二叉树");
        }
    }

    //中序遍历，同时判断是否递增
    private void inOrderRecru(TreeNode treeNode) {
        //这是一个递归方法，要有结束的边界条件,当没有子节点时返回
        if (treeNode == null) {
            return;
        }
        //①先遍历子树的左子树
        this.inOrderRecru(treeNode.getLeft());
        //②与前一个结点值比较
        //访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回false；否则继续遍历
        if (treeNode.getValue() < temp) {
            flag = false;
            return;
        }
        temp = treeNode.getValue();
        //③遍历子树的右子树
        this.inOrderRecru(treeNode.getRight());
    }
}
